#ifndef __SBTPL_H__
#define __SBTPL_H__

#if _MSC_VER
#pragma once
#pragma warning(push)
#pragma warning(disable:4127)	// L4, conditional expression is constant
#pragma warning(disable:4624)	// L1, cannot create destructor
#endif

#ifdef __cplusplus

#include "sbcs.h"
#include <new>

//////////////////////////////////////////////////////////////////////////
// tpl the templates





















//////////////////////////////////////////////////////////////////////////
// class definition
#if _SB_CPP11_CLS_
#define KCS_DELETE						= delete
#define KCS_DEFAULT						= default
#else
#define KCS_DELETE
#define KCS_DEFAULT
#endif

//
#define KCH_NOCTOR(cls)					private: cls() KCS_DELETE
#define KCH_NODTOR(cls)					private: ~cls() KCS_DELETE
#define KCH_NOCOPY(cls)					private: cls(const cls&) KCS_DELETE; cls& operator=(cls const&) KCS_DELETE
#define KCH_NOEQ(cls)					private: void operator==(cls const&) const KCS_DELETE; void operator !=(cls const&) const KCS_DELETE
#define KCH_NOEC(cls)					KCH_NOEQ(cls); KCH_NOCOPY(cls)

#define KCH_SELF(cls)					public: typedef cls this_type
#define KCH_SUPER(cls)					public: typedef cls super_type

#define KCH_DERIVE(cls,spr)				KCH_SELF(cls); KCH_SUPER(spr)
#define KCH_BASE(cls,spr)				KCH_DERIVE(cls,spr); KCH_NOCOPY(cls); KCH_NOEQ(cls)
#define KCH_SEAL(cls)					KCH_NOCTOR(cls); KCH_NOCOPY(cls); KCH_NOEQ(cls)

#define KCH_FRIEND(cls)					friend class cls
#define KCH_INTERN(cls)					public: class cls

#define KCH_OPNEW(cls)					public: void* operator new(size_t size) { return k_allocf(size); }; void operator delete(void* ptr) { k_free(ptr); }
#define KCH_OPNEWVEC(cls)				public: void* operator new[](size_t size) { return k_allocf(size); }; void operator delete[](void* ptr) { k_free(ptr); }
#define KCH_OPNEWREPLACE(cls)			public: void* operator new(size_t, void* ptr) { return ptr; }; void operator delete(void*, void*) {}

#if __GNUC__ || _SB_PPC_
#define KCH_AVOID_FOR_INTERFACE(cls)	virtual ~cls() {}
#else
#define KCH_AVOID_FOR_INTERFACE(cls)	~cls() {}
#endif

namespace tpl
{
	// no copy class
	class NoCopyClass
	{
	protected:
		NoCopyClass() {}
		~NoCopyClass() {}

	private:
		NoCopyClass(NoCopyClass const&) KCS_DELETE;
#if _SB_CPP11_MOVE_
		NoCopyClass(NoCopyClass&&) KCS_DELETE;
#endif
		const NoCopyClass& operator=(NoCopyClass const&) KCS_DELETE;
	};

	// sealed
	class SealClass
	{
	protected:
		SealClass() KCS_DELETE;
		~SealClass() KCS_DELETE;

	private:
		SealClass(SealClass const&) KCS_DELETE;
#if _SB_CPP11_MOVE_
		SealClass(SealClass&&) KCS_DELETE;
#endif
		const SealClass& operator=(SealClass const&)KCS_DELETE;

		void operator==(SealClass const&) const KCS_DELETE;
		void operator!=(SealClass const&) const KCS_DELETE;
	};
}























//////////////////////////////////////////////////////////////////////////
// type classes
namespace tpl
{
	// type trait
	namespace TypeTrait
	{
		// test float
		template <typename T> struct IsFloat { enum { value = false }; };
		template <> struct IsFloat<float> { enum { value = true }; };
		template <> struct IsFloat<double> { enum { value = true }; };
		template <> struct IsFloat<long double> { enum { value = true }; };

		// test integral
		template <typename T> struct IsInt { enum { value = false }; };
		template <> struct IsInt<ksbyte> { enum { value = true }; };
		template <> struct IsInt<kshort> { enum { value = true }; };
		template <> struct IsInt<kint> { enum { value = true }; };
		template <> struct IsInt<klong> { enum { value = true }; };
		template <> struct IsInt<kbyte> { enum { value = true }; };
		template <> struct IsInt<kushort> { enum { value = true }; };
		template <> struct IsInt<kuint> { enum { value = true }; };
		template <> struct IsInt<kulong> { enum { value = true }; };
		template <> struct IsInt<bool> { enum { value = true }; };
		template <> struct IsInt<kchar> { enum { value = true }; };
		template <> struct IsInt<kwchar> { enum { value = true }; };

		// test signed integral
		template <typename T> struct IsSint { enum { value = false }; };
		template <> struct IsSint<ksbyte> { enum { value = true }; };
		template <> struct IsSint<kshort> { enum { value = true }; };
		template <> struct IsSint<kint> { enum { value = true }; };
		template <> struct IsSint<klong> { enum { value = true }; };

		// test unsigned integral
		template <typename T> struct IsUint { enum { value = false }; };
		template <> struct IsUint<kbyte> { enum { value = true }; };
		template <> struct IsUint<kushort> { enum { value = true }; };
		template <> struct IsUint<kuint> { enum { value = true }; };
		template <> struct IsUint<kulong> { enum { value = true }; };
		template <> struct IsUint<kvshort> { enum { value = true }; };
		template <> struct IsUint<kvint> { enum { value = true }; };
		template <> struct IsUint<kvlong> { enum { value = true }; };

		// test arithmetic
		template <typename T> struct IsArithmetic { enum { value = IsFloat<T>::value || IsInt<T>::value }; };

		// test void
		template <typename T> struct IsVoid { enum { value = false }; };
		template <> struct IsVoid<void> { enum { value = true }; };
		template <> struct IsVoid<void const> { enum { value = true }; };
		template <> struct IsVoid<void volatile> { enum { value = true }; };
		template <> struct IsVoid<void const volatile> { enum { value = true }; };

		// test char
		template <typename T> struct IsChar { enum { value = false }; };
		template <> struct IsChar<char> { enum { value = true }; };
		template <> struct IsChar<kwchar> { enum { value = true }; };
#if !_SB_WINDOWS_
		template <> struct IsChar<kucs2char> { enum { value = true }; };
#endif
#if _SB_WINDOWS_
		template <> struct IsChar<kucs4char> { enum { value = true }; };
#endif

		// test pointer
		template <typename T> struct IsPtr { enum { value = false }; };
		template <typename T> struct IsPtr<T*> { enum { value = true }; };
		template <typename T> struct IsPtr<const T*> { enum { value = true }; };
		template <typename T> struct IsPtr<const T* const> { enum { value = true }; };
		template <typename T> struct IsPtr<volatile T*> { enum { value = true }; };
		template <typename T> struct IsPtr<volatile T* const> { enum { value = true }; };

		// test funcdamental
		template <typename T> struct IsFundamental { enum { value = IsArithmetic<T>::value || IsVoid<T>::value }; };

		// test POD
		template <typename T> struct IsPOD { enum { value = __is_pod(T) || __is_enum(T) || IsArithmetic<T>::value || IsPtr<T>::value }; };

		// test equal type
		template <typename A, typename B> struct IsEqual { enum { value = false }; };
		template <typename A> struct IsEqual<A, A> { enum { value = true }; };

		// test array
		template <typename T> struct IsArray { enum { value = false }; };
		template <typename T, ksize_t N> struct IsArray<T[N]> { enum { value = true }; };

		// remove const
		template <typename T> struct RemoveConst { typedef T type; };
		template <typename T> struct RemoveConst<const T> { typedef T type; };

		// remove reference
		template <typename T> struct RemoveRef { typedef T type; };
		template <typename T> struct RemoveRef<T&> { typedef T type; };
#if _SB_CPP11_MOVE_
		template <typename T> struct RemoveRef<T&&> { typedef T type; };
#endif

		// movable
		template <typename T, typename U> struct MovableBase { typename U copy_type; };
#if _SB_CPP11_MOVE_
		template <typename T> struct MovableBase<T, const T&> { typedef const T& copy_type; typedef T&& move_type; };
#else
		template <typename T> struct MovableBase<T, const T&> { typedef const T& copy_type; };
#endif

		// right-value to left-vaue
		template <typename T> struct RvalueToLvalueRef { typedef T type; };
		template <typename T> struct RvalueToLvalueRef<T&&> { typedef T& type; };

		// copy qualifier
		template <typename F, typename T> struct CopyQualifier { typedef T type; };
		template <typename F, typename T> struct CopyQualifier<const F, T> { typedef const T type; };
		template <typename F, typename T> struct CopyQualifier<volatile F, T> { typedef volatile T type; };
		template <typename F, typename T> struct CopyQualifier<const volatile F, T> { typedef const volatile T type; };
	}

	// call trait
	namespace CallTrait
	{
		template <typename T, bool B>
		struct ParamType
		{
			typedef const T& param_type;
			typedef const T& const_param_type;
		};

		template <typename T>
		struct ParamType<T, true>
		{
			typedef const T param_type;
			typedef const T const_param_type;
		};

		template <typename T>
		struct ParamType<T*, true>
		{
			typedef T* param_type;
			typedef const T* const_param_type;
		};

		template <typename T>
		struct CallTypeBase
		{
			enum { value = TypeTrait::IsArithmetic<T>::value || TypeTrait::IsPtr<T>::value || (sizeof(T) <= sizeof(void*) && TypeTrait::IsPOD<T>::value) };
			typedef T value_type;
			typedef T& reference_type;
			typedef const T& const_reference_type;
			typedef typename ParamType<T, value>::param_type param_type;
			typedef typename ParamType<T, value>::const_param_type const_param_type;
		};

		template <typename T> 
		struct CallType : public CallTypeBase<T> {};

		template <typename T>
		struct CallType<T&>
		{
			typedef T value_type;
			typedef T& reference_type;
			typedef const T& const_reference_type;
			typedef T& param_type;
			typedef T& const_param_type;
		};

		template <typename T, ksize_t N>
		struct CallType<T[N]>
		{
			typedef T array_type[N];
			typedef const T* value_type;
			typedef array_type& reference_type;
			typedef const array_type& const_reference_type;
			typedef const T& param_type;
			typedef const T& const_param_type;
		};

		template <typename T, ksize_t N>
		struct CallType<const T[N]>
		{
			typedef const T array_type[N];
			typedef const T* value_type;
			typedef array_type& reference_type;
			typedef const array_type& const_reference_type;
			typedef const T& param_type;
			typedef const T& const_param_type;
		};
	}

	// type trait, continue
	namespace TypeTrait
	{
		// movable
		template <typename T> struct Movable : MovableBase<T, typename CallTrait::CallType<T>::param_type> {};
	}
}























//////////////////////////////////////////////////////////////////////////
// memory classes
namespace tpl
{
	// memory trait
	namespace MemTrait
	{
		template <typename T>
		static void Construct(T* p)
		{
			::new (p)T();
		}

		template <typename T>
		static void Construct(T* p, const T& value)
		{
			::new (p)T(value);
		}

#if _SB_CPP11_MOVE_
		template <typename T>
		static void Construct(T* p, const T&& value)
		{
			::new (p)T(value);
		}
#endif

		template <typename T, typename ITER>
		static void Construct(T* p, ITER begin, ITER end)
		{
			for (ITER it = begin; it != end; ++it)
			{
				::new (p)T(*it);
				p++;
			}
		}

		template <typename T>
		static void ConstructN(T* p, ksize_t count)
		{
			for (ksize_t i = 0; i < count; i++)
#if _MSC_VER && _MSC_VER < 1800
				::new (p + i) T;
#else
				::new (p + i) T();
#endif
		}

		template <typename T>
		static void ConstructN(T* p, ksize_t count, const T& value)
		{
			for (ksize_t i = 0; i < count; i++)
				::new (p + i) T(value);
		}

		template <typename T>
		static void ConstructR(T* p, ksize_t start, ksize_t end)
		{
			for (ksize_t i = start; i < end; i++)
#if _MSC_VER && _MSC_VER < 1800
				::new (p + i) T;
#else
				::new (p + i) T();
#endif
		}

		template <typename T>
		static void ConstructR(T* p, ksize_t start, ksize_t end, const T& value)
		{
			for (ksize_t i = start; i < end; i++)
				::new (p + i) T(value);
		}

		template <typename T>
		static void ConstructF(T* begin, T* end, const T& value)
		{
			for (T* p = begin; p != end; ++p)
				::new (p)T(value);
		}

		template <typename T>
		static void Destruct(T* p)
		{
			p->~T();
			K_NOUSE(p);
		}

		template <typename T>
		static void Destruct(T* begin, T* end)
		{
			for (T* p = begin; p != end; ++p)
				p->~T();
		}

		template <typename T>
		static void DestructN(T* p, ksize_t count)
		{
			for (ksize_t i = 0; i < count; i++)
				p[i].~T();
			K_NOUSE(p);
		}

		template <typename T>
		static void DestructR(T* p, ksize_t start, ksize_t end)
		{
			for (ksize_t i = start; i < end; i++)
				p[i].~T();
			K_NOUSE(p);
		}

		template <typename T>
		static void Reconstruct(T* p)
		{
			p->~T();
			::new (p)T();
		}

		template <typename T>
		static void Reconstruct(T* p, const T& value)
		{
			p->~T();
			::new (p)T(value);
		}
	};

	// memory class
	class MemBase
	{
	protected:
		MemBase() {}
		~MemBase() {}

	public:
		void* operator new(size_t size, const char* file, int line) 
		{
			return k_allocf_dbg(size, file, line); 
		}

		void* operator new(size_t size)
		{
			return k_allocf(size); 
		}

		void* operator new(size_t /*size*/, void* ptr)
		{
			return ptr; 
		}

		void* operator new[](size_t size, const char* file, int line)
		{
			return k_allocf_dbg(size, file, line); 
		}

		void* operator new[](size_t size) 
		{
			return k_allocf(size); 
		}

		void operator delete(void* ptr, const char*, int) 
		{ 
			k_free(ptr); 
		}

		void operator delete(void* ptr) 
		{
			k_free(ptr); 
		}

		void operator delete(void* /*ptr*/, void* /*ptr*/)
		{
		}

		void operator delete[](void* ptr, const char*, int) 
		{
			k_free(ptr); 
		}

		void operator delete[](void* ptr) 
		{
			k_free(ptr); 
		}
	};

	// memory class
	class MemZero
	{
	protected:
		MemZero() {}
		~MemZero() {}

	public:
		void* operator new(size_t size, const char* file, int line)
		{
			return k_alloc_dbg(size, file, line);
		}

		void* operator new(size_t size)
		{
			return k_alloc(size);
		}

		void* operator new(size_t /*size*/, void* ptr)
		{
			return ptr;
		}

		void* operator new[](size_t size, const char* file, int line)
		{
			return k_alloc_dbg(size, file, line);
		}

		void* operator new[](size_t size)
		{
			return k_alloc(size);
		}

		void operator delete(void* ptr, const char*, int)
		{
			k_free(ptr);
		}

		void operator delete(void* ptr)
		{
			k_free(ptr);
		}

		void operator delete(void* /*ptr*/, void* /*ptr*/)
		{
		}

		void operator delete[](void* ptr, const char*, int)
		{
			k_free(ptr);
		}

		void operator delete[](void* ptr)
		{
			k_free(ptr);
		}
	};

	// memory allocator for STL
	template <typename T>
	class STLAllocator
	{
	public:
		typedef T value_type;
		typedef value_type* pointer;
		typedef const value_type* const_pointer;
		typedef value_type& reference;
		typedef const value_type& const_reference;
		typedef std::size_t size_type;
		typedef std::ptrdiff_t difference_type;

		template <typename U> 
		struct rebind 
		{
			typedef STLAllocator<U> other;
		};

		STLAllocator() {}
		STLAllocator(const STLAllocator&) {}
		template <typename U> STLAllocator(const STLAllocator<U>&) {}
		~STLAllocator() {}

		pointer address(reference v) const
		{
			return &v; 
		}

		const_pointer address(const_reference v) const
		{ 
			return &v; 
		}

		//pointer allocate(size_type n, typename std::allocator<void>::const_pointer* dummy = NULL)
		pointer allocate(size_type n, const void* dummy = NULL)
		{ 
			void* ptr = k_allocf(n * sizeof(T)); 
			return (pointer)ptr; // no std::bad_alloc() 
		}

		void deallocate(pointer ptr, size_type) 
		{ 
			k_free((void*)ptr); 
		}

		void construct(pointer ptr)
		{
			::new (static_cast<void*>(ptr)) value_type();
		}

		void construct(pointer ptr, const_reference x) 
		{
			::new (static_cast<void*>(ptr)) value_type(x);
		}

		void destroy(pointer ptr) 
		{
			ptr->~value_type(); 
		}

		size_type max_size() const
		{
			return static_cast<size_type>(-1) / sizeof(T);
		}

	private:
		void operator=(const STLAllocator&);
	};

	template <typename T> 
	inline bool operator==(const STLAllocator<T>&, const STLAllocator<T>&)
	{ 
		return true; 
	}

	template <typename T> 
	inline bool operator!=(const STLAllocator<T>&, const STLAllocator<T>&)
	{ 
		return false; 
	}
}	// tpl




















//////////////////////////////////////////////////////////////////////////
// utility class
namespace tpl
{

	// pair
	template <typename T1, typename T2>
	class Pair
	{
	public:
		typedef Pair<T1, T2> this_type;
		typedef T1 first_type;
		typedef T2 second_type;

	public:
		T1	first;
		T2	second;

	public:
		Pair()
			: first(T1()), second(T2())
		{
		}

		Pair(const T1& t1, const T2& t2)
			: first(t1), second(t2)
		{
		}

		template <typename O1, typename O2>
		Pair(const Pair<O1, O2>& right)
			: first(right.first), second(right.second)
		{
		}

		bool operator==(const Pair& right)
		{
			return this->first == right.first && this->second == right.second;
		}

		bool operator!=(const Pair& right)
		{
			return !((*this) == right);
		}

		bool operator<(const Pair& right)
		{
			return this->first < right.first || !(right.first < this->first) && this->second<right.second;
		}

		bool operator>(const Pair& right)
		{
			return right < (*this);
		}

		bool operator<=(const Pair& right)
		{
			return !(right < (*this));
		}

		bool operator>=(const Pair& right)
		{
			return !((*this) < right);
		}

		void Swap(this_type& right)
		{
			if (this != &right)
			{
				tpl::Swap(first, right.first);
				tpl::Swap(second, right.second);
			}
		}
	};

	// non function1
	template <typename T>
	class DoNothing
#if defined(_FUNCTIONAL_) || defined(_STL_FUNCTION_H)
		: public std::unary_function<T, void>
#endif
	{
	public:
		void operator()(T&) const
		{
		}
	};

	// anycallback
	class AnyCallback : public kanycb
	{
	public:
		AnyCallback(kfunc func, kpointer data = NULL)
		{
			this->func = func;
			this->data = data;
		}

		AnyCallback& operator=(const AnyCallback& right)
		{
			this->func = right.func;
			this->data = right.data;
			return *this;
		}

		bool operator==(const AnyCallback& right)
		{
			return this->func == right.func && this->data == right.data;
		}

		bool operator!=(const AnyCallback& right)
		{
			return this->func != right.func || this->data != right.data;
		}
	};

	// lock guard = std::lock_guard
	template <typename T>
	class LockGuard : public T::ScopedLock
	{
		typedef LockGuard<T> this_type;
		typedef typename T::ScopedLock super_type;

	public:
		LockGuard(T& l)
			: super_type(l)
		{
		}

		operator bool()
		{
			return false;
		}
	};

	// lock guard for pointer
	template <typename T>
	class LockPtrGuard : public T::ScopedLock
	{
		typedef LockPtrGuard<T> this_type;
		typedef typename T::ScopedLock super_type;

	public:
		LockPtrGuard(T* l)
			: super_type(l)
		{
		}

		operator bool()
		{
			return false;
		}
	};

	// scope memory
	template <typename T>
	class ScopedMem : private NoCopyClass
	{
	public:
		enum Mode
		{
			ByAlloc,
			ByNew,
			ByVecNew,
		};

	private:
		T* o;
		Mode mode;

	public:
		ScopedMem(T* right, Mode mode = ByAlloc)
			: o(right), mode(mode)
		{
		}

		explicit ScopedMem(ksize_t count)
			: o(k_new(count, T)), mode(ByAlloc)
		{
		}

		~ScopedMem()
		{
			if (o)
			{
				switch (mode)
				{
					case ByAlloc:
						k_delete(o);
						break;

					case ByNew:
						delete o;
						break;

					case ByVecNew:
						delete[] o;
						break;
				}
			}
		}

		T& operator*()
		{
			return *o;
		}

		T* operator->()
		{
			return o;
		}

		T& operator[](ksize_t index)
		{
			return o[index];
		}

		T* Data()
		{
			return o;
		}

		operator bool() const
		{
			return o != NULL;
		}

		bool operator!() const
		{
			return !o;
		}
	};

	// scope memory of ptr
	template <typename T>
	class ScopedMemPtrAlloc : private NoCopyClass
	{
	private:
		T o;

	public:
		ScopedMemPtrAlloc(T right)
			: o(right)
		{
		}

		~ScopedMemPtrAlloc()
		{
			if (o)
				k_delete(o);
		}

		T Ptr()
		{
			return o;
		}

		operator bool() const
		{
			return o != NULL;
		}

		bool operator!() const
		{
			return !o;
		}

		operator T() const
		{
			return o;
		}
	};

	// scope memory of ptr
	template <typename T>
	class ScopedMemPtrNew : private NoCopyClass
	{
	private:
		T o;

	public:
		ScopedMemPtrNew(T right)
			: o(right)
		{
		}

		~ScopedMemPtrNew()
		{
			if (o)
				delete o;
		}

		T Ptr()
		{
			return o;
		}

		operator bool() const
		{
			return o != NULL;
		}

		bool operator!() const
		{
			return !o;
		}

		operator T() const
		{
			return o;
		}
	};
}




















//////////////////////////////////////////////////////////////////////////
// utility function
namespace tpl
{
	// swap
	template <typename T>
	inline void Swap(T& a, T& b)
	{
		T t = a;
		a = b;
		b = t;
	}

	// swap for left type
	template <typename L, typename R>
	inline void SwapL(L& a, R& b)
	{
		L t = a;
		a = (L)b;
		b = (R)t;
	}

	// swap for right type
	template <typename L, typename R>
	inline void SwapR(L& a, R& b)
	{
		R t = b;
		b = (R)a;
		a = (L)t;
	}

#if _SB_CPP11_MOVE_
	// move
	template <typename T>
	inline typename TypeTrait::RemoveRef<T>::type&& Move(T&& a)
	{
		return (typename TypeTrait::RemoveRef<T>::type&&)a;
	}
#endif

	// move
	template <typename T>
	inline void Move(T& a, typename TypeTrait::Movable<T>::copy_type b)
	{
		MemTrait::Destruct(&a);
		MemTrait::Construct(&a, b);
	}

#if _SB_CPP11_MOVE_
	// move
	template <typename T>
	inline void Move(T& a, typename TypeTrait::Movable<T>::move_type b)
	{
		MemTrait::Destruct(&a);
		MemTrait::Construct(&a, Move(b));
	}
#endif

	// foeach
	template <typename IT, typename FN>
	inline FN ForEach(IT begin, IT end, FN fn)
	{
		for (; begin != end; ++begin)
			fn(*begin);
		return fn;
	}

	// find
	template <typename IT, typename VT>
	inline IT Find(IT begin, IT end, const VT& value)
	{
		for (; begin != end; ++begin)
			if (*begin == value)
				break;
		return begin;
	}

	// str find
	inline const char* Find(const char* begin, const char* end, int value)
	{
		begin = (const char*)memchr(begin, value, end - begin);
		return begin == NULL ? end : begin;
	}

	// find if
	template <typename IT, typename PRFN>
	inline IT FindIf(IT begin, IT end, PRFN pred)
	{
		for (; begin != end; ++begin)
		{
			if (pred(*begin))
				break;
		}
		return begin;
	}

	// find adjacent
	template <typename IT>
	inline IT FindAdj(IT begin, IT end)
	{
		if (begin != end)
		{
			for (IT it; (it = begin), ++begin != end;)
			{
				if (*it == *begin)
					return it;
			}
		}
		return end;
	}

	// find adjacent if
	template <typename IT, typename PRFN>
	inline IT FindAdj(IT begin, IT end, PRFN pred)
	{
		if (begin != end)
		{
			for (IT it; (it = begin), ++begin != end;)
			{
				if (pred(*it, *begin))
					return it;
			}
		}
		return end;
	}

	// minimum element
	template <typename IT>
	inline IT MinElement(IT begin, IT end)
	{
		IT it = begin;
		for (; ++begin != end;)
		{
			if (*begin < *it)
				it = begin;
		}
		return it;
	}

	// minimum element
	template <typename IT, class PRED>
	inline IT MinElement(IT begin, IT end, PRED pred)
	{
		IT it = begin;
		for (; ++begin != end;)
		{
			if (pred(*begin, *it))
				it = begin;
		}
		return it;
	}

	// maximum element
	template <typename IT>
	inline IT MaxElement(IT begin, IT end)
	{
		IT it = begin;
		for (; ++begin != end;)
		{
			if (*it < *begin)
				it = begin;
		}
		return it;
	}

	// maximum element
	template <typename IT, class PRED>
	inline IT MaxElement(IT begin, IT end, PRED pred)
	{
		IT it = begin;
		for (; ++begin != end;)
		{
			if (pred(*it, *begin))
				it = begin;
		}
		return it;
	}

#if _SB_CPP11_MOVE_
	// forward
	template <typename T>
	inline T&& Forward(typename TypeTrait::RemoveRef<T>::type& b)
	{
		return (T&&)b;
	}

	// forward
	template <typename T>
	inline T&& Forward(typename TypeTrait::RemoveRef<T>::type&& b)
	{
		return (T&&)b;
	}
#endif

	// make pair
	template <typename T1, typename T2>
	inline Pair<T1, T2> MakePair(const T1& t1, const T2& t2)
	{
		return Pair<T1, T2>(t1, t2);
	}

	// align
	template <typename T>
	inline T Align(const T ptr, kint align)
	{
		return (T)(((kintptr)ptr + align - 1) & ~(align - 1));
	}

	// align near arbitrary
	template <typename T>
	inline T NearAlign(const T ptr, kint align)
	{
		return (T)((((kintptr)ptr + align - 1) / align) * align);
	}

	// template hash
	template <typename T>
	class Hash
	{
	public:
		typedef T key_type;

		ksize_t operator()(const key_type& key) const
		{
			return k_ptrhash((kpointer)(ksize_t)key);
		}
	};

	// const char* hash
	class HashCharPtr
	{
	public:
		typedef char* key_type;

		ksize_t operator()(const char* key) const
		{
			return k_strhash(key);
		}
	};

	// const wchar* hash
	class HashWcharPtr
	{
	public:
		typedef kwchar* key_type;

		ksize_t operator()(const kwchar* key) const
		{
			return k_wcshash(key);
		}
	};

	// template equalto
	template <typename T>
	class EqTo
#if defined(_FUNCTIONAL_) || defined(_STL_FUNCTION_H)
		: public std::binary_function<T, T, bool>
#endif
	{
	public:
		bool operator()(const T& left, const T& right) const
		{
			return left == right;
		}
	};

	// const char* equals
	class EqToCharPtr
#if defined(_FUNCTIONAL_) || defined(_STL_FUNCTION_H)
		: public std::binary_function<const char*, const char*, bool>
#endif
	{
	public:
		bool operator()(const char* left, const char* right) const
		{
			return k_strcmp(left, right) == 0;
		}
	};

	// const wchar* equals
	class EqToWcharPtr
#if defined(_FUNCTIONAL_) || defined(_STL_FUNCTION_H)
		: public std::binary_function<const kwchar*, const kwchar*, bool>
#endif
	{
	public:
		bool operator()(const kwchar* left, const kwchar* right) const
		{
			return k_wcscmp(left, right) == 0;
		}
	};
}	// tpl




















//////////////////////////////////////////////////////////////////////////
// sort
namespace tpl
{
	namespace _sort
	{
		// heap sink
		template <typename T>
		inline void HeapSink(T* data, ksize_t index, ksize_t count)
		{
			while ((index << 1) < count)
			{
				ksize_t n = index << 1;

				if ((n + 1) < count && data[n] < data[n + 1])
					n++;	// take left

				if (!(data[index] < data[n]))
					return;
				else
				{
					Swap(data[n], data[index]);
					index = n;
				}
			}
		}

		// heap sink, with pred
		template <typename T, typename FN>
		inline void HeapSink(T* data, ksize_t index, ksize_t count, FN pred)
		{
			while ((index << 1) < count)
			{
				ksize_t n = index << 1;

				if ((n + 1) < count && pred(data[n], data[n + 1]))
					n++;

				if (!pred(data[index], data[n]))
					return;
				else
				{
					Swap(data[n], data[index]);
					index = n;
				}
			}
		}

		// quick sink
		template <typename T>
		inline void QuickSink(T* data, kssize_t left, kssize_t right)
		{
			kssize_t l = left, r = right, p = left;

			do
			{
				while (data[l] < data[p])
					++l;
				while (data[p] < data[r])
					--r;

				if (l <= r)
					Swap(data[l++], data[r--]);
			} while (l < r);

			if (left < r)
				QuickSink(data, left, r);

			if (right > l)
				QuickSink(data, l, right);
		}

		// quick sink, with pred
		template <typename T, typename FN>
		inline void QuickSink(T* data, kssize_t left, kssize_t right, FN pred)
		{
			kssize_t l = left, r = right, p = left;

			do
			{
				while (pred(data[l], data[p]))
					++l;
				while (pred(data[p], data[r]))
					--r;

				if (l <= r)
					Swap(data[l++], data[r--]);
			} while (l < r);

			if (left < r)
				QuickSink(data, left, r, pred);

			if (right > l)
				QuickSink(data, l, right, pred);
		}
	}

	// heap sort
	template <typename T>
	inline void HeapSort(T* data, ksize_t size)
	{
		T* heap = data - 1;
		ksize_t count = size + 2;

		for (kssize_t i = (((kssize_t)size - 1) / 2); i >= 0; --i)
			_sort::HeapSink(heap, i + 1, count - 1);

		for (kssize_t i = (kssize_t)size - 1; i >= 0; --i)
		{
			Swap(data[0], data[i]);
			_sort::HeapSink(heap, 1, i + 1);
		}
	}

	// heap sort
	template <typename T, typename FN>
	inline void HeapSort(T* data, ksize_t size, FN pred)
	{
		T* heap = data - 1;
		ksize_t count = size + 2;

		for (kssize_t i = (((kssize_t)size - 1) / 2); i >= 0; --i)
			_sort::HeapSink(heap, i + 1, count - 1, pred);

		for (kssize_t i = (kssize_t)size - 1; i >= 0; --i)
		{
			Swap(data[0], data[i]);
			_sort::HeapSink(heap, 1, i + 1, pred);
		}
	}

	// quick sort
	template <typename T>
	inline void QuickSort(T* data, ksize_t size)
	{
		_sort::QuickSink(data, 0, (kssize_t)size - 1);
	}

	// quick sort
	template <typename T, typename FN>
	inline void QuickSort(T* data, ksize_t size, FN pred)
	{
		_sort::QuickSink(data, 0, (kssize_t)size - 1, pred);
	}
}






















//////////////////////////////////////////////////////////////////////////
// ptr traits
namespace tpl
{
	//////////////////////////////////////////////////////////////////////////
	// load & unload ptr
	template <typename BASETYPE>
	class BasePtr
	{
	private:
		BASETYPE* _ptr;

	public:
		K_NOTHROW BasePtr() : _ptr(NULL)
		{
		}

		K_NOTHROW BasePtr(BASETYPE* ptr, bool isload = true)
			: _ptr(ptr) 
		{
			if (ptr && isload) 
				ptr->Load(); 
		}

		K_NOTHROW BasePtr(const BasePtr& o)
			: _ptr(o._ptr) 
		{ 
			if (_ptr) 
				_ptr->Load(); 
		}

		template <typename EITHERTYPE> 
		K_NOTHROW BasePtr(const BasePtr<EITHERTYPE>& o)
			: _ptr(o._ptr) 
		{ 
			if (_ptr) 
				_ptr->Load(); 
		}

		K_NOTHROW ~BasePtr()
		{ 
			if (_ptr) 
			{
				_ptr->Unload(); 
				k_qccd(_ptr = NULL); 
			} 
		}

		K_NOTHROW BasePtr& operator=(BASETYPE* right)
		{
			base_type* prev = _ptr;
			_ptr = right;
			if (_ptr)
				_ptr->Load();
			if (prev)
				prev->Unload();
			return *this;
		}

		K_NOTHROW BasePtr& operator=(const BasePtr& right)
		{
			return *this = right._ptr;
		}

		template <typename EITHERTYPE>
		K_NOTHROW BasePtr& operator=(const BasePtr<EITHERTYPE>& right)
		{
			return *this = right._ptr;
		}

		template <typename EITHERTYPE>
		K_NOTHROW bool operator==(const BasePtr<EITHERTYPE>& right)
		{
			return _ptr == right._ptr;
		}

		K_NOTHROW BASETYPE* operator->() const
		{
			return _ptr; 
		}

		K_NOTHROW operator BASETYPE*() const
		{
			return _ptr;
		}

		K_NOTHROW BASETYPE& operator*() const
		{
			return *_ptr; 
		}

		K_NOTHROW BASETYPE** operator&()
		{
			return &_ptr; 
		}

		K_NOTHROW bool operator!() const
		{
			return !_ptr; 
		}

		K_NOTHROW operator bool() const
		{
			return _ptr != NULL; 
		}

		K_NOTHROW BASETYPE** InitPtr()
		{
			*this = NULL;
			return &_ptr;
		}

		K_NOTHROW BASETYPE* Ptr() const
		{
			return _ptr;
		}

		K_NOTHROW friend bool TestPtr(const BasePtr& ptr)
		{
			return ptr._ptr != NULL;
		}

		K_NOTHROW void SafeUnload()
		{
			*this = NULL;
		}

		K_NOTHROW kint SafeGetRef()
		{
			if (_ptr == NULL)
				return 0;
			else
			{
				_ptr->Load();
				return _ptr->Unload();
			}
		}

		K_NOTHROW void Swap(BasePtr& ptr)
		{
			BASETYPE* tmp = _ptr;
			_ptr = ptr._ptr;
			ptr._ptr = tmp;
		}
	};

	template <typename T, typename U> 
	inline bool operator==(const BasePtr<T>& l, const BasePtr<U>& r)
	{
		return l.Ptr() == r.Ptr();
	}

	template <typename T>
	inline bool operator==(const BasePtr<T>& l, const T* r)
	{
		return l.Ptr() == r;
	}

	template <typename T>
	inline bool operator==(const T* l, const BasePtr<T>& r)
	{
		return r == l.Ptr();
	}

	template <typename T, typename U>
	inline bool operator!=(const BasePtr<T>& l, const BasePtr<U>& r)
	{
		return l.Ptr() != r.Ptr();
	}

	template <typename T>
	inline bool operator!=(const BasePtr<T>& l, const T* r)
	{
		return l.Ptr() != r;
	}

	template <typename T>
	inline bool operator!=(const T* l, const BasePtr<T>& r)
	{
		return r != l.Ptr();
	}
}	// tpl






















//////////////////////////////////////////////////////////////////////////
// function
namespace tpl
{
	namespace _traits
	{
		template <typename T> inline static T BadFunctionCall()
		{
			k_assert(0, "bad function call.");
			return (T)0;
		}

#if _MSC_VER
		template <> inline static void BadFunctionCall<void>()
#else
		template <> inline void BadFunctionCall<void>()
#endif
		{
		}
	}

	//
	template <typename T>
	class Function;

	//
	template <typename R>
	class Function<R()>
	{
	private:
		union
		{
			kpointer obj;
			kpointer ptr[8];
		} _impl;

	public:
		Function()
		{
			_impl.obj = NULL;
		}

		Function(const Function& right)
		{
			FuncBase* ptr = (FuncBase*)&right._impl;
			ptr->Copy(&_impl);
		}

		template <typename T>
		Function(const T& right)
		{
			::new ((FuncBase*)&_impl) FuncImpl<T>(right);
		}

		template <typename P, typename F>
		Function(const P& obj, const F& func)
		{
			::new ((FuncBase*)&_impl) FuncImpl<Pair<P, F> >(MakePair(obj, func));
		}

	public:
		operator bool() const
		{
			return _impl.obj != NULL;
		}

		bool operator!() const
		{
			return _impl.obj == NULL;
		}

		template <typename T>
		Function& operator=(const T& right)
		{
			::new (static_cast<FuncBase*>(&_impl)) FuncImpl<T>(right);
			return *this;
		}

		Function& operator=(const Function& right)
		{
			if (this != &right)
			{
				FuncBase* ptr = (FuncBase*)&right._impl;
				ptr->Copy(&_impl);
			}
			return *this;
		}

		R operator()() const
		{
			if (_impl.obj == NULL)
				return _traits::BadFunctionCall<R>();
			else
			{
				FuncBase* ptr = (FuncBase*)&_impl;
				return ptr->Call();
			}
		}

		void Reset()
		{
			_impl.obj = NULL;
		}

	private:
		struct FuncBase
		{
			virtual ~FuncBase() {}
			virtual void Copy(kpointer ptr) const = 0;
			virtual R Call() const = 0;
		};

		template <typename T>
		struct FuncImpl : public FuncBase
		{
			T _callee;

			FuncImpl(const T& right)
				: _callee(right)
			{
			}

			FuncImpl(const FuncImpl& right)
				: _callee(right._callee)
			{
			}

			void Copy(kpointer ptr) const
			{
				::new ((FuncImpl*)ptr) FuncImpl(*this);
			}

			const T& Get() const
			{
				return _callee;
			}

			R Call() const
			{
				return FuncInvoke<T>::Call(this->_callee);
			}

			template <typename F>
			struct FuncInvoke
			{
				static R Call(const F& f)
				{
					return (const_cast<F&>(f))();
				}
			};

			template <typename P, typename F>
			struct FuncInvoke<Pair<P, F> >
			{
				static R Call(const Pair<P, F>& mf)
				{
					return ((*mf.first).*mf.second)();
				}
			};
		};
	};

	//
	template <typename R, typename T1>
	class Function<R(T1)>
	{
	private:
		union
		{
			kpointer obj;
			kpointer ptr[8];
		} _impl;

	public:
		Function()
		{
			_impl.obj = NULL;
		}

		Function(const Function& right)
		{
			FuncBase* ptr = (FuncBase*)&right._impl;
			ptr->Copy(&_impl);
		}

		template <typename T>
		Function(const T& right)
		{
			::new ((FuncBase*)&_impl) FuncImpl<T>(right);
		}

		template <typename P, typename F>
		Function(const P& obj, const F& func)
		{
			::new ((FuncBase*)&_impl) FuncImpl<Pair<P, F> >(MakePair(obj, func));
		}

	public:
		operator bool() const
		{
			return _impl.obj != NULL;
		}

		bool operator!() const
		{
			return _impl.obj == NULL;
		}

		template <typename T>
		Function& operator=(const T& right)
		{
			::new (static_cast<FuncBase*>(&_impl)) FuncImpl<T>(right);
			return *this;
		}

		Function& operator=(const Function& right)
		{
			if (this != &right)
			{
				FuncBase* ptr = (FuncBase*)&right._impl;
				ptr->Copy(&_impl);
			}
			return *this;
		}

		R operator()(T1 t1) const
		{
			if (_impl.obj == NULL)
				return _traits::BadFunctionCall<R>();
			else
			{
				FuncBase* ptr = (FuncBase*)&_impl;
				return ptr->Call(t1);
			}
		}

		void Reset()
		{
			_impl.obj = NULL;
		}

	private:
		struct FuncBase
		{
			virtual ~FuncBase() {}
			virtual void Copy(kpointer ptr) const = 0;
			virtual R Call(T1) const = 0;
		};

		template <typename T>
		struct FuncImpl : public FuncBase
		{
			T _callee;

			FuncImpl(const T& right)
				: _callee(right)
			{
			}

			FuncImpl(const FuncImpl& right)
				: _callee(right._callee)
			{
			}

			void Copy(kpointer ptr) const
			{
				::new ((FuncImpl*)ptr) FuncImpl(*this);
			}

			const T& Get() const
			{
				return _callee;
			}

			R Call(T1 t1) const
			{
				return FuncInvoke<T>::Call(this->_callee, t1);
			}

			template <typename F>
			struct FuncInvoke
			{
				static R Call(const F& f, T1 t1)
				{
					return (const_cast<F&>(f))(t1);
				}
			};

			template <typename P, typename F>
			struct FuncInvoke<Pair<P, F> >
			{
				static R Call(const Pair<P, F>& mf, T1 t1)
				{
					return ((*mf.first).*mf.second)(t1);
				}
			};
		};
	};

	//
	template <typename R, typename T1, typename T2>
	class Function<R(T1, T2)>
	{
	private:
		union
		{
			kpointer obj;
			kpointer ptr[8];
		} _impl;

	public:
		Function()
		{
			_impl.obj = NULL;
		}

		Function(const Function& right)
		{
			FuncBase* ptr = (FuncBase*)&right._impl;
			ptr->Copy(&_impl);
		}

		template <typename T>
		Function(const T& right)
		{
			::new ((FuncBase*)&_impl) FuncImpl<T>(right);
		}

		template <typename P, typename F>
		Function(const P& obj, const F& func)
		{
			::new ((FuncBase*)&_impl) FuncImpl<Pair<P, F> >(MakePair(obj, func));
		}

	public:
		operator bool() const
		{
			return _impl.obj != NULL;
		}

		bool operator!() const
		{
			return _impl.obj == NULL;
		}

		template <typename T>
		Function& operator=(const T& right)
		{
			::new (static_cast<FuncBase*>(&_impl)) FuncImpl<T>(right);
			return *this;
		}

		Function& operator=(const Function& right)
		{
			if (this != &right)
			{
				FuncBase* ptr = (FuncBase*)&right._impl;
				ptr->Copy(&_impl);
			}
			return *this;
		}

		R operator()(T1 t1, T2 t2) const
		{
			if (_impl.obj == NULL)
				return _traits::BadFunctionCall<R>();
			else
			{
				FuncBase* ptr = (FuncBase*)&_impl;
				return ptr->Call(t1, t2);
			}
		}

		void Reset()
		{
			_impl.obj = NULL;
		}

	private:
		struct FuncBase
		{
			virtual ~FuncBase() {}
			virtual void Copy(kpointer ptr) const = 0;
			virtual R Call(T1, T2) const = 0;
		};

		template <typename T>
		struct FuncImpl : public FuncBase
		{
			T _callee;

			FuncImpl(const T& right)
				: _callee(right)
			{
			}

			FuncImpl(const FuncImpl& right)
				: _callee(right._callee)
			{
			}

			void Copy(kpointer ptr) const
			{
				::new ((FuncImpl*)ptr) FuncImpl(*this);
			}

			const T& Get() const
			{
				return _callee;
			}

			R Call(T1 t1, T2 t2) const
			{
				return FuncInvoke<T>::Call(this->_callee, t1, t2);
			}

			template <typename F>
			struct FuncInvoke
			{
				static R Call(const F& f, T1 t1, T2 t2)
				{
					return (const_cast<F&>(f))(t1, t2);
				}
			};

			template <typename P, typename F>
			struct FuncInvoke<Pair<P, F> >
			{
				static R Call(const Pair<P, F>& mf, T1 t1, T2 t2)
				{
					return ((*mf.first).*mf.second)(t1, t2);
				}
			};
		};
	};

	//
	template <typename R, typename T1, typename T2, typename T3>
	class Function<R(T1, T2, T3)>
	{
	private:
		union
		{
			kpointer obj;
			kpointer ptr[8];
		} _impl;

	public:
		Function()
		{
			_impl.obj = NULL;
		}

		Function(const Function& right)
		{
			FuncBase* ptr = (FuncBase*)&right._impl;
			ptr->Copy(&_impl);
		}

		template <typename T>
		Function(const T& right)
		{
			::new ((FuncBase*)&_impl) FuncImpl<T>(right);
		}

		template <typename P, typename F>
		Function(const P& obj, const F& func)
		{
			::new ((FuncBase*)&_impl) FuncImpl<Pair<P, F> >(MakePair(obj, func));
		}

	public:
		operator bool() const
		{
			return _impl.obj != NULL;
		}

		bool operator!() const
		{
			return _impl.obj == NULL;
		}

		template <typename T>
		Function& operator=(const T& right)
		{
			::new (static_cast<FuncBase*>(&_impl)) FuncImpl<T>(right);
			return *this;
		}

		Function& operator=(const Function& right)
		{
			if (this != &right)
			{
				FuncBase* ptr = (FuncBase*)&right._impl;
				ptr->Copy(&_impl);
			}
			return *this;
		}

		R operator()(T1 t1, T2 t2, T3 t3) const
		{
			if (_impl.obj == NULL)
				return _traits::BadFunctionCall<R>();
			else
			{
				FuncBase* ptr = (FuncBase*)&_impl;
				return ptr->Call(t1, t2, t3);
			}
		}

		void Reset()
		{
			_impl.obj = NULL;
		}

	private:
		struct FuncBase
		{
			virtual ~FuncBase() {}
			virtual void Copy(kpointer ptr) const = 0;
			virtual R Call(T1, T2, T3) const = 0;
		};

		template <typename T>
		struct FuncImpl : public FuncBase
		{
			T _callee;

			FuncImpl(const T& right)
				: _callee(right)
			{
			}

			FuncImpl(const FuncImpl& right)
				: _callee(right._callee)
			{
			}

			void Copy(kpointer ptr) const
			{
				::new ((FuncImpl*)ptr) FuncImpl(*this);
			}

			const T& Get() const
			{
				return _callee;
			}

			R Call(T1 t1, T2 t2, T3 t3) const
			{
				return FuncInvoke<T>::Call(this->_callee, t1, t2, t3);
			}

			template <typename F>
			struct FuncInvoke
			{
				static R Call(const F& f, T1 t1, T2 t2, T3 t3)
				{
					return (const_cast<F&>(f))(t1, t2, t3);
				}
			};

			template <typename P, typename F>
			struct FuncInvoke<Pair<P, F> >
			{
				static R Call(const Pair<P, F>& mf, T1 t1, T2 t2, T3 t3)
				{
					return ((*mf.first).*mf.second)(t1, t2, t3);
				}
			};
		};
	};

	//
	template <typename R, typename T1, typename T2, typename T3, typename T4>
	class Function<R(T1, T2, T3, T4)>
	{
	private:
		union
		{
			kpointer obj;
			kpointer ptr[8];
		} _impl;

	public:
		Function()
		{
			_impl.obj = NULL;
		}

		Function(const Function& right)
		{
			FuncBase* ptr = (FuncBase*)&right._impl;
			ptr->Copy(&_impl);
		}

		template <typename T>
		Function(const T& right)
		{
			::new ((FuncBase*)&_impl) FuncImpl<T>(right);
		}

		template <typename P, typename F>
		Function(const P& obj, const F& func)
		{
			::new ((FuncBase*)&_impl) FuncImpl<Pair<P, F> >(MakePair(obj, func));
		}

	public:
		operator bool() const
		{
			return _impl.obj != NULL;
		}

		bool operator!() const
		{
			return _impl.obj == NULL;
		}

		template <typename T>
		Function& operator=(const T& right)
		{
			::new (static_cast<FuncBase*>(&_impl)) FuncImpl<T>(right);
			return *this;
		}

		Function& operator=(const Function& right)
		{
			if (this != &right)
			{
				FuncBase* ptr = (FuncBase*)&right._impl;
				ptr->Copy(&_impl);
			}
			return *this;
		}

		R operator()(T1 t1, T2 t2, T3 t3, T4 t4) const
		{
			if (_impl.obj == NULL)
				return _traits::BadFunctionCall<R>();
			else
			{
				FuncBase* ptr = (FuncBase*)&_impl;
				return ptr->Call(t1, t2, t3, t4);
			}
		}

		void Reset()
		{
			_impl.obj = NULL;
		}

	private:
		struct FuncBase
		{
			virtual ~FuncBase() {}
			virtual void Copy(kpointer ptr) const = 0;
			virtual R Call(T1, T2, T3, T4) const = 0;
		};

		template <typename T>
		struct FuncImpl : public FuncBase
		{
			T _callee;

			FuncImpl(const T& right)
				: _callee(right)
			{
			}

			FuncImpl(const FuncImpl& right)
				: _callee(right._callee)
			{
			}

			void Copy(kpointer ptr) const
			{
				::new ((FuncImpl*)ptr) FuncImpl(*this);
			}

			const T& Get() const
			{
				return _callee;
			}

			R Call(T1 t1, T2 t2, T3 t3, T4 t4) const
			{
				return FuncInvoke<T>::Call(this->_callee, t1, t2, t3, t4);
			}

			template <typename F>
			struct FuncInvoke
			{
				static R Call(const F& f, T1 t1, T2 t2, T3 t3, T4 t4)
				{
					return (const_cast<F&>(f))(t1, t2, t3, t4);
				}
			};

			template <typename P, typename F>
			struct FuncInvoke<Pair<P, F> >
			{
				static R Call(const Pair<P, F>& mf, T1 t1, T2 t2, T3 t3, T4 t4)
				{
					return ((*mf.first).*mf.second)(t1, t2, t3, t4);
				}
			};
		};
	};

	//
	template <typename R, typename T1, typename T2, typename T3, typename T4, typename T5>
	class Function<R(T1, T2, T3, T4, T5)>
	{
	private:
		union
		{
			kpointer obj;
			kpointer ptr[8];
		} _impl;

	public:
		Function()
		{
			_impl.obj = NULL;
		}

		Function(const Function& right)
		{
			FuncBase* ptr = (FuncBase*)&right._impl;
			ptr->Copy(&_impl);
		}

		template <typename T>
		Function(const T& right)
		{
			::new ((FuncBase*)&_impl) FuncImpl<T>(right);
		}

		template <typename P, typename F>
		Function(const P& obj, const F& func)
		{
			::new ((FuncBase*)&_impl) FuncImpl<Pair<P, F> >(MakePair(obj, func));
		}

	public:
		operator bool() const
		{
			return _impl.obj != NULL;
		}

		bool operator!() const
		{
			return _impl.obj == NULL;
		}

		template <typename T>
		Function& operator=(const T& right)
		{
			::new (static_cast<FuncBase*>(&_impl)) FuncImpl<T>(right);
			return *this;
		}

		Function& operator=(const Function& right)
		{
			if (this != &right)
			{
				FuncBase* ptr = (FuncBase*)&right._impl;
				ptr->Copy(&_impl);
			}
			return *this;
		}

		R operator()(T1 t1, T2 t2, T3 t3, T4 t4, T5 t5) const
		{
			if (_impl.obj == NULL)
				return _traits::BadFunctionCall<R>();
			else
			{
				FuncBase* ptr = (FuncBase*)&_impl;
				return ptr->Call(t1, t2, t3, t4);
			}
		}

		void Reset()
		{
			_impl.obj = NULL;
		}

	private:
		struct FuncBase
		{
			virtual ~FuncBase() {}
			virtual void Copy(kpointer ptr) const = 0;
			virtual R Call(T1, T2, T3, T4, T5) const = 0;
		};

		template <typename T>
		struct FuncImpl : public FuncBase
		{
			T _callee;

			FuncImpl(const T& right)
				: _callee(right)
			{
			}

			FuncImpl(const FuncImpl& right)
				: _callee(right._callee)
			{
			}

			void Copy(kpointer ptr) const
			{
				::new ((FuncImpl*)ptr) FuncImpl(*this);
			}

			const T& Get() const
			{
				return _callee;
			}

			R Call(T1 t1, T2 t2, T3 t3, T4 t4, T5 t5) const
			{
				return FuncInvoke<T>::Call(this->_callee, t1, t2, t3, t4, t5);
			}

			template <typename F>
			struct FuncInvoke
			{
				static R Call(const F& f, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5)
				{
					return (const_cast<F&>(f))(t1, t2, t3, t4, t5);
				}
			};

			template <typename P, typename F>
			struct FuncInvoke<Pair<P, F> >
			{
				static R Call(const Pair<P, F>& mf, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5)
				{
					return ((*mf.first).*mf.second)(t1, t2, t3, t4, t5);
				}
			};
		};
	};
}






















//////////////////////////////////////////////////////////////////////////
// stl & boost application
namespace tpl
{
	// string
#if defined(_XSTRING_)
	typedef std::basic_string<char, std::char_traits<char>, STLAllocator<char> > string;
	typedef std::basic_string<kwchar, std::char_traits<kwchar>, STLAllocator<kwchar> > wstring;
#endif

	// vector
#if defined(_VECTOR_)
	template <typename T, typename A = STLAllocator<T> >
	class vector : public std::vector<T, A>, public MemBase
	{
	public:
		typedef tpl::vector<T, A> this_type;
		typedef std::vector<T, A> super_type;

	public:
		vector(void)
			: super_type()
		{
		}

		explicit vector(size_type count)
			: super_type(count)
		{
		}

		vector(size_type count, const T &value)
			: super_type(count, value)
		{
		}

		vector(const this_type &right)
			: super_type(right)
		{
		}

		template<typename ITER>
		vector(ITER frst, ITER last)
			: super_type(frst, last)
		{
		}

#if _SB_CPP11_MOVE_
		vector(this_type&& right)
			: super_type(right)
		{	
		}
#endif
	};
#endif

	// list
#if defined(_LIST_)
	template <typename T, typename A = STLAllocator<T> >
	class list : public std::list<T, A>, public MemBase
	{
	public:
		typedef tpl::list<T, A> this_type;
		typedef std::list<T, A> super_type;

	public:
		list(void)
			: super_type()
		{
		}

		explicit list(size_type count)
			: super_type(count)
		{
		}

		list(size_type count, const T &value)
			: super_type(count, value)
		{
		}

		list(const this_type &right)
			: super_type(right)
		{
		}

		template<typename ITER>
		list(ITER frst, ITER last)
			: super_type(frst, last)
		{
		}

#if _SB_CPP11_MOVE_
		list(this_type&& right)
			: super_type(right)
		{
		}
#endif
	};
#endif

	// deque
#if defined(_DEQUE_)
	template <typename T, typename A = STLAllocator<T> >
	class deque : public std::deque<T, A>, public MemBase
	{
	public:
		typedef tpl::deque<T, A> this_type;
		typedef std::deque<T, A> super_type;

	public:
		deque(void)
			: super_type()
		{
		}

		explicit deque(size_type count)
			: super_type(count)
		{
		}

		deque(size_type count, const T &value)
			: super_type(count, value)
		{
		}

		deque(const this_type &rhs)
			: super_type(rhs)
		{
		}

		template<typename ITER>
		deque(ITER frst, ITER last)
			: super_type(frst, last)
		{
		}

#if _SB_CPP11_MOVE_
		deque(this_type&& right)
			: super_type(right)
		{
		}
#endif
	};
#endif

	// queue
#if defined(_QUEUE_)
	template<typename T, typename C = deque<T> >
	class queue : public std::queue<T, C>, public MemBase
	{
	public:
		typedef tpl::queue<T, ContainerT> this_type;
		typedef std::queue<T, ContainerT> super_type;

	public:
		queue(void)
			: super_type()
		{
		}

		queue(const this_type& right)
			: super_type(right)
		{
		}

		explicit queue(const ContainerT &container)
			: super_type(container)
		{
		}

#if _SB_CPP11_MOVE_
		queue(this_type&& right)
			: super_type(right)
		{
		}

		queue(C&& cont)
			: super_type(cont)
		{
		}
#endif
	};
#endif

	// set
#if defined(_SET_)
	template<typename T, typename P = std::less<T>, typename A = Allocator<T> >
	class set : public std::set<T, P, A>, public MemBase
	{
	public:
		typedef tpl::set<T, P, A> this_type;
		typedef std::set<T, P, A> super_type;

	public:
		set(void)
			: super_type()
		{
		}

		explicit set(const key_compare &pred)
			: super_type(pred)
		{
		}

		template<typename ITER>
		set(ITER frst, ITER last)
			: super_type(frst, last)
		{
		}

		template<typename ITER>
		set(ITER frst, ITER last, const key_compare &pred)
			: super_type(frst, last, pred)
		{
		}

		set(const this_type& right)
			: super_type(right)
		{
		}

#if _SB_CPP11_MOVE_
		set(this_type&& right)
			: super_type(right)
		{
		}
#endif
	};
#endif

	// map
#if defined(_MAP_)
	template<typename K, typename V, 
		typename P = std::less<K>,
		typename A = STLAllocator<std::pair<K, V> > >
	class map : public std::map<K, V, P, A>, public MemBase
	{
	public:
		typedef tpl::map<K, V, P, A> this_type;
		typedef std::map<K, V, P, A> super_type;

	public:
		map(void)
			: super_type()
		{
		}

		explicit map(const key_compare &pred)
			: super_type(pred)
		{
		}

		template<typename ITER>
		map(ITER frst, ITER last)
			: super_type(frst, last)
		{
		}

		template<typename ITER>
		map(ITER frst, ITER last, const key_compare &pred)
			: super_type(frst, last, pred)
		{
		}

		map(const this_type& right)
			: super_type(right)
		{
		}

#if _SB_CPP11_MOVE_
		map(this_type&& right)
			: super_type(right)
		{
		}
#endif
	};
#endif

	// multi set
#if defined(_SET_)
	template<typename K,
		typename P = std::less<K>,
		typename A = STLAllocator<K> >
	class multiset : public std::multiset<K, P, A>, public MemBase
	{
	public:
		typedef tpl::multiset<K, P, A> this_type;
		typedef std::multiset<K, P, A> super_type;

	public:
		multiset(void)
			: super_type()
		{
		}

		explicit multiset(const key_compare &pred)
			: super_type(pred)
		{
		}

		template<typename ITER>
		multiset(ITER frst, ITER last)
			: super_type(frst, last)
		{
		}

		template<typename ITER>
		multiset(ITER frst, ITER last, const key_compare &pred)
			: super_type(frst, last, pred)
		{
		}

		multiset(const this_type& right)
			: super_type(right)
		{
		}

#if _SB_CPP11_MOVE_
		multiset(this_type&& right)
			: super_type(right)
		{
		}
#endif
	};
#endif

	// multi map
#if defined(_MAP_)
	template<typename K, typename V,
		typename P = std::less<K>,
		typename A = STLAllocator<std::pair<K, V> > >
	class multimap : public std::multimap<K, V, P, A>, public MemBase
	{
	public:
		typedef tpl::multimap<K, V, P, A> this_type;
		typedef std::multimap<K, V, P, A> super_type;

	public:
		multimap(void)
			: super_type()
		{
		}

		explicit multimap(const key_compare &pred)
			: super_type(pred)
		{
		}

		template<typename ITER>
		multimap(ITER frst, ITER last)
			: super_type(frst, last)
		{
		}

		template<typename ITER>
		multimap(ITER frst, ITER last, const key_compare &pred)
			: super_type(frst, last, pred)
		{
		}

		multimap(const this_type& right)
			: super_type(right)
		{
		}

#if _SB_CPP11_MOVE_
		multimap(this_type&& right)
			: super_type(right)
		{
		}
#endif
	};
#endif

	// unordered map
#if defined(_UNORDERED_MAP_)
	template<typename K, typename V, 
		typename H = std::hash<Key>, typename P = std::equal_to<K>, 
		typename A = STLAllocator<K> >
	class unordered_map : public std::unordered_map<K, V, H, P, A>, public MemBase
	{
	public:
		typedef tpl::unordered_map<K, V, H, P, A> this_type;
		typedef std::unordered_map<K, V, H, P, A> super_type;

	public:
		unordered_map()
			: super_type()
		{
		}

		unordered_map(const this_type& right)
			: super_type(right)
		{
		}

		explicit unordered_map(size_type buckets)
			: super_type(buckets)
		{
		}

		unordered_map(size_type buckets, const hasher& hasharg)
			: super_type(buckets, hasharg)
		{
		}

		unordered_map(size_type buckets, const hasher& hasharg, const _Keyeq& keyeqarg)
			: super_type(buckets, hasharg, keyeqarg)
		{
		}

		template<class ITER>
		unordered_map(ITER frst, ITER last)
			: super_type(frst, last)
		{
		}

		template<class ITER>
		unordered_map(ITER frst, ITER last, size_type buckets)
			: super_type(frst, last, buckets)
		{
		}

		template<class ITER>
		unordered_map(ITER frst, ITER last, size_type buckets, const hasher& hasharg)
			: super_type(frst, last, buckets, hasharg)
		{
		}

		template<class ITER>
		unordered_map(ITER frst, ITER last, size_type buckets, const hasher& hasharg, const _Keyeq& keyeqarg)
			: super_type(frst, last, buckets, hasharg, keyeqarg)
		{
		}

#if _SB_CPP11_MOVE_
		unordered_map(this_type&& right)
			: super_type(right)
		{
		}
#endif
	};
#endif

	// from boost
	namespace _boost
	{
		// foreach
		class foreach_iter
		{
		private:
			void* _myIt;
			bool  _runOnce;

		public:
			template <class Iter>
			foreach_iter(Iter it) 
				: _runOnce(true)
			{ 
				_myIt = new Iter; 
				*((Iter*)_myIt) = it;
			}

			virtual ~foreach_iter()
			{
				if (_myIt)
				{
					k_assert(0, "bad foreach iterator");
					k_exit(0);
				}
			}

			template <class Iter>
			Iter& increase(Iter it)
			{
				return ++(*((Iter*)_myIt)); 
			}

			template <class Iter>
			Iter& get(Iter it) 
			{
				return *((Iter*)_myIt); 
			}

			template <class Iter>
			bool all_done(Iter it) 
			{
				bool ret = *((Iter*)_myIt) == it; 
				if (ret) 
					cleanup(it); 
				return ret; 
			}

			bool run_once() 
			{
				bool ret = _runOnce; 
				_runOnce = ret ? false : true; 
				return ret; 
			}

		private:
			template <class Iter>
			void cleanup(Iter it) 
			{
				if (_myIt) 
				{
					delete ((Iter*)_myIt); 
					_myIt = 0; 
				} 
			}
		};
	}
}

#if _SB_CPP11_FOR_
#define BOOST_FOREACH(VAR, COL) \
	for (VAR : COL)
#else
#define BOOST_FOREACH(VAR, COL) \
	for (tpl::_boost::foreach_iter it((COL).begin()); !it.all_done((COL).end()); it.increase((COL).begin())) \
		for (VAR = *(it.get((COL).begin())); it.run_once();)
#endif

#define kForEach(VAR, COL) BOOST_FOREACH(VAR, COL)






















#endif	// __cplusplus

#if _MSC_VER
#pragma warning(pop)
#endif

#endif	// __SBTPL_H__
